import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;


public class Ex6_4 {

	public Ex6_4() {}

	public static void main(String[] args) {
		Ex6_4 ex64 = new Ex6_4();
		HashMap<String,ArrayList<String>> graph = 
				Utils.readWeightedGraph(
						"C:\\Users\\josemfer\\Downloads\\dataset_74_7.txt");
		Integer source = 7;
		Integer sink = 23;
		ex64.getLongestPath(graph, source, sink);

	}

	
	public void backtrackGraph(HashMap<String,ArrayList<String>> aGraph) {
		
	}
	
	public void getLongestPath(HashMap<String,ArrayList<String>> aGraph, 
			Integer source, Integer sink) {
		HashMap<String,Integer> weights = Utils.readGraphWeights(
				"C:\\Users\\josemfer\\Downloads\\dataset_74_7.txt");
		HashMap<String, Integer> sa = new HashMap<String, Integer>();
		HashMap<String, String> backtrack = new HashMap<String,String>();
		HashMap<String,ArrayList<String>> ingoings = Utils.getIngoingGraph(aGraph);
		
		for (Entry<String,ArrayList<String>> entry : aGraph.entrySet()) {
			sa.put(entry.getKey(), -9999);
		}		
		sa.put(String.valueOf(source), 0);
		ArrayList<String> topoOrder = getTopologicalOrder(aGraph);
		
		for (String node : topoOrder) {
			Integer nodeInt = Integer.valueOf(node);
			if (nodeInt >= source && nodeInt <= sink) {
				Integer[] preds = getPredecessorsWeight(aGraph, sa,weights,nodeInt);
				if (preds != null) {
					Integer maxPred = Utils.max(preds);
					sa.put(node, maxPred);
					// choosen predecesor
					String predecessor = ingoings.get(node).get(Utils.maxIndex(preds));
					backtrack.put(node,predecessor);
				}
			}			
		}
		System.out.println(sa.get(String.valueOf(sink)));	
		
		// recover track
		ArrayList<String> track = new ArrayList<String>();
		String node = String.valueOf(sink);
		do {			
			track.add(node);
			node = backtrack.get(node);			
		} while (node != null);
		Collections.reverse(track);
		for (int i=0;i<track.size();i++) {
			String vert = track.get(i);
			System.out.print(vert);
			if (i<track.size()-1) {
				System.out.print("->");
			}
		}
		
	}

	private Integer[] getPredecessorsWeight(HashMap<String,ArrayList<String>> aGraph, 
			HashMap<String, Integer> s, HashMap<String,Integer> weights, Integer node) {		
		ArrayList<String> ingoings = Utils.getIngoingGraph(aGraph).get(String.valueOf(node));
		if (ingoings == null) {
			return null;
		}
		Integer[] results = new Integer[ingoings.size()];
		for (int i=0;i<ingoings.size();i++) {
			String ingoing = ingoings.get(i);
			Integer weight = weights.get(ingoing + "_" + String.valueOf(node));
			Integer totalWeight = weight + s.get(ingoing);
			results[i] = totalWeight;
		}			
		return results;
	}

	public ArrayList<String> getTopologicalOrder(
			HashMap<String,ArrayList<String>> aGraph) {
		//HashMap<String,ArrayList<String>> graph = 
			//	new HashMap<String,ArrayList<String>>(aGraph);		
		HashMap<String,ArrayList<String>> graph = 
						Utils.cloneGraph(aGraph);			
		ArrayList<String> list = new ArrayList<String>();
		ArrayList<String> candidates = Utils.getNodesWithNoIncoming(graph);
		while (!candidates.isEmpty()  ) {
			String node = candidates.get(0);
			list.add(node);
			candidates.remove(0);
			ArrayList<String> outgoings = graph.get(node);
			if (outgoings != null) {
				outgoings = new ArrayList<String>(outgoings);
			} else {
				break;
			}
			for (String outgoing : outgoings) {
				Utils.removeFromGraph(graph, node, outgoing);
				//    if outgoing has no other incoming edges ...
				HashMap<String,Integer> inDegreeMap = Utils.getInDegree(graph);
				Integer indeg = inDegreeMap.get(outgoing);
				if (indeg == null) {
					indeg = 0;
				}
				if ( indeg == 0) {
					candidates.add(outgoing);
				}				
			}
		}
		if (graph.size() > 0) {
			System.out.println("shit!!");
		}		
		return list;
	}


}
